import java.util.*;

public class DoubleCircularList {
    // 定义双向循环链表的节点类
    static class Node {
        int data; // 节点数据
        Node prev; // 指向前驱节点的引用
        Node next; // 指向后继节点的引用
        // 节点构造方法
        Node(int data) {
            this.data = data;
            this.prev = null; // 初始前驱为null
            this.next = null; // 初始后继为null
        }
    }
    Node head; // 头节点（哨兵节点）
    int length; // 链表长度

    // 构造方法初始化链表
    public DoubleCircularList() {
        head = new Node(-1); // 头节点数据-1
        head.prev = head; // 头节点的前驱指向自己
        head.next = head; // 头节点的后继指向自己
        length = 0; // 初始长度0
    }

    // 头插法
    public void addAtHead(int data) {
        Node newNode = new Node(data); // 新建节点
        newNode.next = head.next; // 新节点的next指向原头节点后的第一个节点
        newNode.prev = head; // 新节点的prev指向头节点
        head.next.prev = newNode; // 原头节点后的第一个节点的prev指向新节点
        head.next = newNode; // 头节点的next指向新节点
        length++; // 长度加1
    }

    // 尾插法
    public void addAtTail(int data) {
        Node newNode = new Node(data); // 新建节点
        Node last = head.prev; // 找到尾节点（头节点的prev指向尾节点）
        newNode.prev = last; // 新节点的prev指向尾节点
        newNode.next = head; // 新节点的next指向头节点
        last.next = newNode; // 尾节点的next指向新节点
        head.prev = newNode; // 头节点的prev指向新节点（新尾节点）
        length++; // 长度加1
    }

    // 删除指定数据的节点
    public boolean deleteNode(int data) {
        Node cur = head.next; // 从第一个有效节点开始遍历
        while (cur != head) { // 未遍历完链表
            if (cur.data == data) { // 找到目标节点
                cur.prev.next = cur.next; // 前驱的next指向后继
                cur.next.prev = cur.prev; // 后继的prev指向前驱
                length--; // 长度减1
                return true; // 删除成功
            }
            cur = cur.next; // 继续遍历
        }
        return false; // 未找到，删除失败
    }

    // 反转链表
    public void reverse() {
        Node cur = head.next; // 从第一个有效节点开始
        while (cur != head) { // 遍历链表
            Node temp = cur.prev; // 临时存储前驱节点
            cur.prev = cur.next; // 当前节点的prev指向后继
            cur.next = temp; // 当前节点的next指向前驱
            cur = temp.prev; // 移动到新的节点（原前驱的前驱，即反转后的位置）
        }
        // 调整头节点的前后指针（确保循环链表结构正确）
        head.prev = head.next;
        head.next = head.prev.prev;
    }

    // 打印链表信息
    public void printList() {
        Node cur = head.next; // 从第一个有效节点开始
        System.out.print("head: " + head + "\n"); // 打印头节点地址
        System.out.print("当前链表: ");
        while (cur != head) { // 遍历打印每个节点数据
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
        System.out.println("length: " + length); // 打印长度
    }
}

class DoubleCircularListTest {
    public static void main(String[] args) {
        SingleCircularList linkedList = new SingleCircularList();
        System.out.println("------------初始化链表------------");
        System.out.println("head= 00000000091250 ");

        // 头插法添加结点
        System.out.println("------------增加结点(头插法)------------");
        linkedList.addAtHead(13);
        linkedList.addAtHead(14);
        linkedList.addAtHead(15);
        linkedList.printList();

        // 尾插法添加结点
        System.out.println("------------增加结点(尾插法)------------");
        linkedList.addAtTail(21);
        linkedList.addAtTail(22);
        linkedList.addAtTail(23);
        linkedList.printList();

        // 删除结点
        System.out.println("------------删除结点------------");
        System.out.println("删除数据为5120的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(5120);
        linkedList.printList();

        System.out.println("删除数据为13的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(13);
        linkedList.printList();

        System.out.println("删除数据为23的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(23);
        linkedList.printList();

        // 反转链表
        System.out.println("------------反转链表------------");
        System.out.println("-----反转前");
        linkedList.printList();
        linkedList.reverse();
        System.out.println("-----反转后");
        linkedList.printList();
    }
}